<!DOCTYPE HTML>
<html lang="">
<head>
    <!--Setting-->
    <meta charset="UTF-8">
    <meta name="viewport" content="width=device-width, user-scalable=no, initial-scale=1.0, maximum-scale=1.0, minimum-scale=1.0">
    <meta http-equiv="X-UA-Compatible" content="IE=Edge,chrome=1">
    <meta http-equiv="Cache-Control" content="no-siteapp">
    <meta http-equiv="Cache-Control" content="no-transform">
    <meta name="renderer" content="webkit|ie-comp|ie-stand">
    <meta name="apple-mobile-web-app-capable" content="无限Coding">
    <meta name="apple-mobile-web-app-status-bar-style" content="black">
    <meta name="format-detection" content="telephone=no,email=no,adress=no">
    <meta name="browsermode" content="application">
    <meta name="screen-orientation" content="portrait">
    <link rel="dns-prefetch" href="http://yoursite.com">
    <!--SEO-->





<meta name="robots" content="all" />
<meta name="google" content="all" />
<meta name="googlebot" content="all" />
<meta name="verify" content="all" />
    <!--Title-->


<title>数据结构-线性表|顺序表|链表(中) | 无限Coding</title>


    <link rel="alternate" href="/atom.xml" title="无限Coding" type="application/atom+xml">


    <link rel="icon" href="/favicon.ico">

    



<link rel="stylesheet" href="//cdn.bootcss.com/bootstrap/3.3.4/css/bootstrap.min.css?rev=3.3.4">
<link rel="stylesheet" href="//cdn.bootcss.com/font-awesome/4.7.0/css/font-awesome.min.css">
<link rel="stylesheet" href="/css/style.css?rev=@@hash">




    
	<div class="hide">
		<script type="text/javascript">
			var cnzz_protocol = (("https:" == document.location.protocol) ? " https://" : " http://");document.write(unescape("%3Cspan class='cnzz_stat_icon_1263868967 hide' %3E%3Cscript%20src%3D%22https%3A%2F%2Fs95.cnzz.com%2Fz_stat.php%3Fweb_id%3D1272564536%22%3E%3C%2Fscript%3E%3C/span%3E%3Cscript src='" + cnzz_protocol + "s19.cnzz.com/z_stat.php%3Fid%3D1263868967%26show%3Dpic1' type='text/javascript'%3E%3C/script%3E"));
		</script>
	</div>






    
</head>


<!--[if lte IE 8]>
<style>
    html{ font-size: 1em }
</style>
<![endif]-->
<!--[if lte IE 9]>
<div style="ie">你使用的浏览器版本过低，为了你更好的阅读体验，请更新浏览器的版本或者使用其他现代浏览器，比如Chrome、Firefox、Safari等。</div>
<![endif]-->

<body>
    <header class="main-header"  style="background-image:url(http://oyxhmjutw.bkt.clouddn.com/18-2-21/37655074.jpg)"  >
    <div class="main-header-box">
        <a class="header-avatar" href="/" title="">
            <img src="/img/avatar.jpg" alt="logo头像">
        </a>
        <div class="branding">
        	<!--<h2 class="text-hide">Snippet主题,从未如此简单有趣</h2>-->
            
                 <img src="/img/branding.png" alt="Snippet 博客主题">  
             
    	</div>
    </div>
</header>
    <nav class="main-navigation">
    <div class="container">
        <div class="row">
            <div class="col-sm-12">
                <div class="navbar-header"><span class="nav-toggle-button collapsed" data-toggle="collapse" data-target="#main-menu" id="mnav">
                    <span class="sr-only">Toggle navigation</span>
                    <i class="fa fa-bars"></i>
                    </span>
                </div>
                <div class="collapse navbar-collapse" id="main-menu">
                    <ul class="menu">
                        
                            <li role="presentation"><a href="/"><i class="fa fa-fw "></i>首页</a>
                            </li>
                        
                            <li role="presentation"><a href="/"><i class="fa fa-fw "></i>推荐</a>
                            </li>
                        
                            <li role="presentation"><a href="/"><i class="fa fa-fw "></i>资源</a>
                            </li>
                        
                            <li role="presentation"><a href="/"><i class="fa fa-fw "></i>随想</a>
                            </li>
                        
                            <li role="presentation"><a href="/"><i class="fa fa-fw "></i>关于</a>
                            </li>
                        
                    </ul>
                </div>
            </div>
        </div>
    </div>
</nav>
    <section class="content-wrap">
        <div class="container">
            <div class="row">
                <main class="col-md-8 main-content m-post">
                    <p id="process"></p>
<article class="post">
    <div class="post-head">
        <h1 id="数据结构-线性表|顺序表|链表(中)">
            
	            数据结构-线性表|顺序表|链表(中)
            
        </h1>
        <div class="post-meta">
    
    
    <span class="categories-meta fa-wrap">
        <i class="fa fa-folder-open-o"></i>
        <a href="/categories/数据结构">
            数据结构
        </a>
    </span>
    
    
    <span class="fa-wrap">
        <i class="fa fa-tags"></i>
        <span class="tags-meta">
            
            <a href="/tags/数据结构">
               数据结构
            </a>
            
        </span>
    </span>
    
    
    <span class="fa-wrap">
        <i class="fa fa-clock-o"></i>
        <span class="date-meta">2018/02/18</span>
    </span>
</div>

            
            
    </div>
    
    <div class="post-body post-content">
        <h1 id="数据结构-线性表-顺序表-链表-中"><a href="#数据结构-线性表-顺序表-链表-中" class="headerlink" title="数据结构-线性表|顺序表|链表(中)"></a>数据结构-线性表|顺序表|链表(中)</h1><h2 id="本节纲要"><a href="#本节纲要" class="headerlink" title="本节纲要"></a>本节纲要</h2><ul>
<li>预备知识</li>
<li>顺序表(Sequential List)</li>
<li><strong>单链表(Singly Linked List )</strong></li>
<li><strong>静态链表(Static list )</strong></li>
<li>循环链表(circular linked list)</li>
<li>双向链表(doubly linked list)</li>
</ul>
<a id="more"></a>
<h2 id="03-单链表-Singly-Linked-List"><a href="#03-单链表-Singly-Linked-List" class="headerlink" title="03 单链表(Singly Linked List )"></a>03 单链表(Singly Linked List )</h2><h3 id="3-1-什么是单链表？"><a href="#3-1-什么是单链表？" class="headerlink" title="3.1 什么是单链表？"></a>3.1 什么是单链表？</h3><p>单链表是一种链式存储的结构。它动态的为节点分配存储单元。当有节点插入时，系统动态的为结点分配空间。在结点删除时，应该及时释放相应的存储单元，以防止内存泄露。由于是链式存储，所以操作单链表时，必须知道头结点或者头指针的位置。并且，在查找第i个节点时，必须找到第i-1个节点。</p>
<h3 id="3-2-单链表的存储结构代码描述"><a href="#3-2-单链表的存储结构代码描述" class="headerlink" title="3.2 单链表的存储结构代码描述"></a>3.2 单链表的存储结构代码描述</h3><p>对于链式存储，通过上一节的讲解相信大家已经了解得够清楚了。如下图所示：<br><img src="http://upload-images.jianshu.io/upload_images/10386940-6b9928e162e91a25.png?imageMogr2/auto-orient/strip%7CimageView2/2/w/1240" alt=""></p>
<p>下面我们来看看单链表存储是如何用代码来实现的。<br><figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">//单链表的存储结构C语言代码</span></span><br><span class="line"><span class="keyword">typedef</span> <span class="class"><span class="keyword">struct</span> <span class="title">SListNode</span></span></span><br><span class="line"><span class="class">&#123;</span></span><br><span class="line">    datatype data;    <span class="comment">//数据域</span></span><br><span class="line">    <span class="class"><span class="keyword">struct</span> <span class="title">SListNode</span> * <span class="title">pnext</span>;</span><span class="comment">//指针域</span></span><br><span class="line">&#125;SLinkList;</span><br></pre></td></tr></table></figure></p>
<p>由上面的结构我们可以看出，一个节点由存放数据的数据域和存放地址的指针域组成。假如p指向了第i个节点，那么p-&gt;data就是该节点存放的数据，而p-&gt;pnext自然就是指向下一个节点的指针。如下图所示：<br><img src="http://upload-images.jianshu.io/upload_images/10386940-2fa902f061b0fdfa.png?imageMogr2/auto-orient/strip%7CimageView2/2/w/1240" alt=""></p>
<p>那么接下来我们看看单链表的各个操作具体实现吧。(只讲几个关键步骤)<br>备注：下面的代码基于这样的一个单链表：</p>
<ul>
<li>有一个头指针phead</li>
<li>有一个头结点node</li>
<li>头指针指向头结点，头结点位置记为0<h3 id="3-3-单链表的读取"><a href="#3-3-单链表的读取" class="headerlink" title="3.3 单链表的读取"></a>3.3 单链表的读取</h3>在拿到头指针以后，单链表的读取也并非一件难事。一开始设置一个计数变量，不断遍历链表，让计数器自增。找到合适的位置将数据读取出来。具体代码实现如下：<figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="meta-keyword">define</span> status bool</span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">define</span> ERROR false</span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">define</span> OK true</span></span><br><span class="line"><span class="comment">/*</span></span><br><span class="line"><span class="comment"> * 函数功能：获取位置index节点的数据</span></span><br><span class="line"><span class="comment"> * 参数说明：phead链表头结点，e用来获取的变量，index索引</span></span><br><span class="line"><span class="comment">*/</span></span><br><span class="line"></span><br><span class="line"><span class="function">status <span class="title">GetSListIndexNode</span><span class="params">(Node * phead,DType *e, <span class="keyword">int</span> index)</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">	<span class="keyword">int</span> icount = <span class="number">0</span>; <span class="comment">//计数器</span></span><br><span class="line">    <span class="comment">//注：0号位为头结点，头结点不存放任何数据</span></span><br><span class="line">	<span class="keyword">if</span> (phead-&gt;pnext == <span class="literal">nullptr</span> || index &lt; <span class="number">1</span> || index &gt; GetSListLength()<span class="comment">/*此处为链表长度*/</span>)</span><br><span class="line">	&#123;</span><br><span class="line">		<span class="keyword">return</span> ERROR; <span class="comment">//异常 处理</span></span><br><span class="line">	&#125;</span><br><span class="line">	<span class="keyword">while</span> (phead-&gt;pnext != <span class="literal">nullptr</span>)</span><br><span class="line">	&#123;</span><br><span class="line">		icount++;</span><br><span class="line">		phead = phead-&gt;pnext;</span><br><span class="line">		<span class="keyword">if</span> (icount == index)</span><br><span class="line">		&#123;</span><br><span class="line">			*e = phead-&gt;data;</span><br><span class="line">			<span class="keyword">return</span> OK;</span><br><span class="line">		&#125;</span><br><span class="line">	&#125;</span><br><span class="line">	<span class="keyword">return</span> ERROR;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
</li>
</ul>
<h3 id="3-4-单链表的插入"><a href="#3-4-单链表的插入" class="headerlink" title="3.4 单链表的插入"></a>3.4 单链表的插入</h3><h4 id="3-4-1-指定位置后插"><a href="#3-4-1-指定位置后插" class="headerlink" title="3.4.1 指定位置后插"></a>3.4.1 指定位置后插</h4><p>其实链表的插入和删除都是很简单的操作，初学者只要抓住指针指向的节点，并加以区分开来，就很easy了。如下图：<br><img src="http://upload-images.jianshu.io/upload_images/10386940-44961ddce9ca5a82.png?imageMogr2/auto-orient/strip%7CimageView2/2/w/1240" alt=""></p>
<p>图中，假如此时p指向了我们要插入的节点的位置。那么，怎样把我们的S节点给插入到p指向的节点之后？在这里我们先不要惊动p以及p后面的节点：</p>
<ol>
<li>我们先让S节点指向p之后的节点(步骤①)</li>
<li>之后我们切断p和p后面那个节点的关系(步骤②)</li>
<li>最后让p节点的指针域指向s节点(步骤③)，搞定</li>
</ol>
<p>算法描述：</p>
<ol>
<li>声明一个指针p指向链表头结点，向后遍历p=p-&gt;next，找到正确的位置。</li>
<li>新建一个结点s。</li>
<li>s-&gt;next = p-&gt;next ①</li>
<li>p-&gt;next = s       ②③<br>具体代码如下：<figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="meta-keyword">define</span> status bool</span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">define</span> ERROR false</span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">define</span> OK true</span></span><br><span class="line"><span class="comment">/*</span></span><br><span class="line"><span class="comment"> * 函数功能：指定位置后插</span></span><br><span class="line"><span class="comment"> * 参数说明：phead链表头结点，IData插入的数据，index索引</span></span><br><span class="line"><span class="comment">*/</span></span><br><span class="line"><span class="function">status <span class="title">InsertSListNodeFront</span><span class="params">(Node * phead, DType IData, <span class="keyword">int</span> index)</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">	<span class="keyword">if</span> (phead-&gt;pnext == <span class="literal">nullptr</span> || index &lt; <span class="number">1</span> || index &gt; GetSListLength())</span><br><span class="line">	&#123;</span><br><span class="line">		<span class="keyword">return</span> ERROR; <span class="comment">//异常 处理</span></span><br><span class="line">	&#125;</span><br><span class="line">	<span class="keyword">int</span> iCount = <span class="number">0</span>; <span class="comment">//计数器</span></span><br><span class="line">	Node&lt;DType&gt; * q = <span class="literal">nullptr</span>; <span class="comment">//备用</span></span><br><span class="line">	<span class="keyword">while</span> (phead-&gt;pnext != <span class="literal">nullptr</span>)</span><br><span class="line">	&#123;</span><br><span class="line">		iCount++;</span><br><span class="line">		q = phead;</span><br><span class="line">		phead = phead-&gt;pnext;</span><br><span class="line">		<span class="keyword">if</span> ( iCount == index )</span><br><span class="line">		&#123;</span><br><span class="line">			Node&lt;DType&gt; * p = <span class="keyword">new</span> Node&lt;DType&gt;;</span><br><span class="line">			p-&gt;data = IData;</span><br><span class="line">			p-&gt;pnext = phead;</span><br><span class="line">			q-&gt;pnext = p;   <span class="comment">//前插</span></span><br><span class="line">			<span class="keyword">return</span> OK;</span><br><span class="line">		&#125;</span><br><span class="line">	&#125;</span><br><span class="line">	<span class="keyword">return</span> ERROR;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
</li>
</ol>
<h4 id="3-4-1-指定位置前插"><a href="#3-4-1-指定位置前插" class="headerlink" title="3.4.1 指定位置前插"></a>3.4.1 指定位置前插</h4><p>咳咳，聪明的小伙伴，用脑子想想。指定位置前插 == 指定位置的前一个位置进行后插。懂了吧？直接看具体代码：<br><figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">/*</span></span><br><span class="line"><span class="comment"> * 函数功能：指定位置后插</span></span><br><span class="line"><span class="comment"> * 参数说明：phead链表头结点，IData插入的数据，index索引</span></span><br><span class="line"><span class="comment">*/</span></span><br><span class="line"><span class="function">status <span class="title">InsertSListNodeBack</span><span class="params">(Node * phead, DType IData, <span class="keyword">int</span> index)</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">	<span class="keyword">if</span> (phead-&gt;pnext == <span class="literal">nullptr</span> || index &lt; <span class="number">1</span> || index &gt; GetSListLength())</span><br><span class="line">	&#123;</span><br><span class="line">		<span class="keyword">return</span> ERROR; <span class="comment">//异常 处理</span></span><br><span class="line">	&#125;</span><br><span class="line">	<span class="keyword">int</span> iCount = <span class="number">0</span>; <span class="comment">//计数器</span></span><br><span class="line">	Node&lt;DType&gt; * q = <span class="literal">nullptr</span>; <span class="comment">//备用</span></span><br><span class="line">	<span class="keyword">while</span> (phead-&gt;pnext != <span class="literal">nullptr</span>)</span><br><span class="line">	&#123;</span><br><span class="line">		iCount++;</span><br><span class="line">		q = phead;</span><br><span class="line">		phead = phead-&gt;pnext;</span><br><span class="line">		<span class="keyword">if</span> (iCount == index)</span><br><span class="line">		&#123;</span><br><span class="line">			Node&lt;DType&gt; * p = <span class="keyword">new</span> Node&lt;DType&gt;;</span><br><span class="line">			q = phead;</span><br><span class="line">			phead = phead-&gt;pnext; <span class="comment">//后插就是后一个节点的前插咯</span></span><br><span class="line">			p-&gt;data = IData;</span><br><span class="line">			p-&gt;pnext = phead;</span><br><span class="line">			q-&gt;pnext = p;   </span><br><span class="line">			<span class="keyword">return</span> OK;</span><br><span class="line">		&#125;</span><br><span class="line">	&#125;</span><br><span class="line">	<span class="keyword">return</span> ERROR;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure></p>
<h3 id="3-5-单链表的删除"><a href="#3-5-单链表的删除" class="headerlink" title="3.5 单链表的删除"></a>3.5 单链表的删除</h3><p>单链表的删除其实也是很简单。只要比如要删除p指向的节点，只需要让p之前的节点的指针域直接指向p之后的节点，再把p给free就OK了。如下图：</p>
<p><img src="http://upload-images.jianshu.io/upload_images/10386940-ea2faa21a4da59c6.png?imageMogr2/auto-orient/strip%7CimageView2/2/w/1240" alt=""></p>
<p>算法描述:</p>
<ol>
<li>声明一个指针p指向链表头结点，向后遍历p=p-&gt;next，找到要删除的节点位置。</li>
<li>q = p-&gt;next</li>
<li>p-&gt;next = q-&gt;next  ①②</li>
<li>free(q)            ③④</li>
</ol>
<p>具体代码如下:<br><figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">/*</span></span><br><span class="line"><span class="comment"> * 函数功能：指定位置后插</span></span><br><span class="line"><span class="comment"> * 参数说明：phead链表头结点，IData获取删除的数据，index索引</span></span><br><span class="line"><span class="comment">*/</span></span><br><span class="line"><span class="comment">//删除指定位置节点(e获取删除元素)</span></span><br><span class="line"><span class="keyword">template</span> &lt;<span class="keyword">typename</span> DType&gt;</span><br><span class="line"><span class="function">status <span class="title">DeleteSListIndexNode</span><span class="params">(Node * phead, DType *e, <span class="keyword">int</span> index)</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">	<span class="keyword">int</span> i = <span class="number">0</span>; <span class="comment">//计数器</span></span><br><span class="line">	Node&lt;DType&gt; * q = <span class="literal">nullptr</span>;</span><br><span class="line">	<span class="keyword">if</span> (phead-&gt;pnext == <span class="literal">nullptr</span> || index &lt; <span class="number">1</span> || index &gt; GetSListLength())</span><br><span class="line">	&#123;</span><br><span class="line">		<span class="keyword">return</span> ERROR; <span class="comment">//异常 处理</span></span><br><span class="line">	&#125;</span><br><span class="line">	<span class="keyword">while</span> (phead-&gt;pnext != <span class="literal">nullptr</span>)</span><br><span class="line">	&#123;</span><br><span class="line">		i++;</span><br><span class="line">		q = phead; <span class="comment">//保存备用</span></span><br><span class="line">		phead = phead-&gt;pnext;</span><br><span class="line">		<span class="keyword">if</span> (i == index)</span><br><span class="line">		&#123;</span><br><span class="line">			*e = phead-&gt;data;</span><br><span class="line">			q-&gt;pnext = phead-&gt;pnext; <span class="comment">//删除出局</span></span><br><span class="line">			<span class="keyword">return</span> OK;</span><br><span class="line">		&#125;</span><br><span class="line">	&#125;</span><br><span class="line">	<span class="keyword">return</span> ERROR;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure></p>
<p>代码应该不难，相信大家都能很容易看懂。</p>
<h3 id="3-6-单链表的完整代码"><a href="#3-6-单链表的完整代码" class="headerlink" title="3.6 单链表的完整代码"></a>3.6 单链表的完整代码</h3><p>好了，前面介绍了几个重要的操作，接下来请大家看看完整的代码吧。小编为了使用方便，就用C++的class和template将整个链表封装到了一个类里面，通过模板实现泛型编程。<br><figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br><span class="line">62</span><br><span class="line">63</span><br><span class="line">64</span><br><span class="line">65</span><br><span class="line">66</span><br><span class="line">67</span><br><span class="line">68</span><br><span class="line">69</span><br><span class="line">70</span><br><span class="line">71</span><br><span class="line">72</span><br><span class="line">73</span><br><span class="line">74</span><br><span class="line">75</span><br><span class="line">76</span><br><span class="line">77</span><br><span class="line">78</span><br><span class="line">79</span><br><span class="line">80</span><br><span class="line">81</span><br><span class="line">82</span><br><span class="line">83</span><br><span class="line">84</span><br><span class="line">85</span><br><span class="line">86</span><br><span class="line">87</span><br><span class="line">88</span><br><span class="line">89</span><br><span class="line">90</span><br><span class="line">91</span><br><span class="line">92</span><br><span class="line">93</span><br><span class="line">94</span><br><span class="line">95</span><br><span class="line">96</span><br><span class="line">97</span><br><span class="line">98</span><br><span class="line">99</span><br><span class="line">100</span><br><span class="line">101</span><br><span class="line">102</span><br><span class="line">103</span><br><span class="line">104</span><br><span class="line">105</span><br><span class="line">106</span><br><span class="line">107</span><br><span class="line">108</span><br><span class="line">109</span><br><span class="line">110</span><br><span class="line">111</span><br><span class="line">112</span><br><span class="line">113</span><br><span class="line">114</span><br><span class="line">115</span><br><span class="line">116</span><br><span class="line">117</span><br><span class="line">118</span><br><span class="line">119</span><br><span class="line">120</span><br><span class="line">121</span><br><span class="line">122</span><br><span class="line">123</span><br><span class="line">124</span><br><span class="line">125</span><br><span class="line">126</span><br><span class="line">127</span><br><span class="line">128</span><br><span class="line">129</span><br><span class="line">130</span><br><span class="line">131</span><br><span class="line">132</span><br><span class="line">133</span><br><span class="line">134</span><br><span class="line">135</span><br><span class="line">136</span><br><span class="line">137</span><br><span class="line">138</span><br><span class="line">139</span><br><span class="line">140</span><br><span class="line">141</span><br><span class="line">142</span><br><span class="line">143</span><br><span class="line">144</span><br><span class="line">145</span><br><span class="line">146</span><br><span class="line">147</span><br><span class="line">148</span><br><span class="line">149</span><br><span class="line">150</span><br><span class="line">151</span><br><span class="line">152</span><br><span class="line">153</span><br><span class="line">154</span><br><span class="line">155</span><br><span class="line">156</span><br><span class="line">157</span><br><span class="line">158</span><br><span class="line">159</span><br><span class="line">160</span><br><span class="line">161</span><br><span class="line">162</span><br><span class="line">163</span><br><span class="line">164</span><br><span class="line">165</span><br><span class="line">166</span><br><span class="line">167</span><br><span class="line">168</span><br><span class="line">169</span><br><span class="line">170</span><br><span class="line">171</span><br><span class="line">172</span><br><span class="line">173</span><br><span class="line">174</span><br><span class="line">175</span><br><span class="line">176</span><br><span class="line">177</span><br><span class="line">178</span><br><span class="line">179</span><br><span class="line">180</span><br><span class="line">181</span><br><span class="line">182</span><br><span class="line">183</span><br><span class="line">184</span><br><span class="line">185</span><br><span class="line">186</span><br><span class="line">187</span><br><span class="line">188</span><br><span class="line">189</span><br><span class="line">190</span><br><span class="line">191</span><br><span class="line">192</span><br><span class="line">193</span><br><span class="line">194</span><br><span class="line">195</span><br><span class="line">196</span><br><span class="line">197</span><br><span class="line">198</span><br><span class="line">199</span><br><span class="line">200</span><br><span class="line">201</span><br><span class="line">202</span><br><span class="line">203</span><br><span class="line">204</span><br><span class="line">205</span><br><span class="line">206</span><br><span class="line">207</span><br><span class="line">208</span><br><span class="line">209</span><br><span class="line">210</span><br><span class="line">211</span><br><span class="line">212</span><br><span class="line">213</span><br><span class="line">214</span><br><span class="line">215</span><br><span class="line">216</span><br><span class="line">217</span><br><span class="line">218</span><br><span class="line">219</span><br><span class="line">220</span><br><span class="line">221</span><br><span class="line">222</span><br><span class="line">223</span><br><span class="line">224</span><br><span class="line">225</span><br><span class="line">226</span><br><span class="line">227</span><br><span class="line">228</span><br><span class="line">229</span><br><span class="line">230</span><br><span class="line">231</span><br><span class="line">232</span><br><span class="line">233</span><br><span class="line">234</span><br><span class="line">235</span><br><span class="line">236</span><br><span class="line">237</span><br><span class="line">238</span><br><span class="line">239</span><br><span class="line">240</span><br><span class="line">241</span><br><span class="line">242</span><br><span class="line">243</span><br><span class="line">244</span><br><span class="line">245</span><br><span class="line">246</span><br><span class="line">247</span><br><span class="line">248</span><br><span class="line">249</span><br><span class="line">250</span><br><span class="line">251</span><br><span class="line">252</span><br><span class="line">253</span><br><span class="line">254</span><br><span class="line">255</span><br><span class="line">256</span><br><span class="line">257</span><br><span class="line">258</span><br><span class="line">259</span><br><span class="line">260</span><br><span class="line">261</span><br><span class="line">262</span><br><span class="line">263</span><br><span class="line">264</span><br><span class="line">265</span><br><span class="line">266</span><br><span class="line">267</span><br><span class="line">268</span><br><span class="line">269</span><br><span class="line">270</span><br><span class="line">271</span><br><span class="line">272</span><br><span class="line">273</span><br><span class="line">274</span><br><span class="line">275</span><br><span class="line">276</span><br><span class="line">277</span><br><span class="line">278</span><br><span class="line">279</span><br><span class="line">280</span><br><span class="line">281</span><br><span class="line">282</span><br><span class="line">283</span><br><span class="line">284</span><br><span class="line">285</span><br><span class="line">286</span><br><span class="line">287</span><br><span class="line">288</span><br><span class="line">289</span><br><span class="line">290</span><br><span class="line">291</span><br><span class="line">292</span><br><span class="line">293</span><br><span class="line">294</span><br><span class="line">295</span><br><span class="line">296</span><br><span class="line">297</span><br><span class="line">298</span><br><span class="line">299</span><br><span class="line">300</span><br><span class="line">301</span><br><span class="line">302</span><br><span class="line">303</span><br><span class="line">304</span><br><span class="line">305</span><br><span class="line">306</span><br><span class="line">307</span><br><span class="line">308</span><br><span class="line">309</span><br><span class="line">310</span><br><span class="line">311</span><br><span class="line">312</span><br><span class="line">313</span><br><span class="line">314</span><br><span class="line">315</span><br><span class="line">316</span><br><span class="line">317</span><br><span class="line">318</span><br><span class="line">319</span><br><span class="line">320</span><br><span class="line">321</span><br><span class="line">322</span><br><span class="line">323</span><br><span class="line">324</span><br><span class="line">325</span><br><span class="line">326</span><br><span class="line">327</span><br><span class="line">328</span><br><span class="line">329</span><br><span class="line">330</span><br><span class="line">331</span><br><span class="line">332</span><br><span class="line">333</span><br><span class="line">334</span><br><span class="line">335</span><br><span class="line">336</span><br><span class="line">337</span><br><span class="line">338</span><br><span class="line">339</span><br><span class="line">340</span><br><span class="line">341</span><br><span class="line">342</span><br><span class="line">343</span><br><span class="line">344</span><br><span class="line">345</span><br><span class="line">346</span><br><span class="line">347</span><br><span class="line">348</span><br><span class="line">349</span><br><span class="line">350</span><br><span class="line">351</span><br><span class="line">352</span><br><span class="line">353</span><br><span class="line">354</span><br><span class="line">355</span><br><span class="line">356</span><br><span class="line">357</span><br><span class="line">358</span><br><span class="line">359</span><br><span class="line">360</span><br><span class="line">361</span><br><span class="line">362</span><br><span class="line">363</span><br><span class="line">364</span><br><span class="line">365</span><br><span class="line">366</span><br><span class="line">367</span><br><span class="line">368</span><br><span class="line">369</span><br><span class="line">370</span><br><span class="line">371</span><br><span class="line">372</span><br><span class="line">373</span><br><span class="line">374</span><br><span class="line">375</span><br><span class="line">376</span><br><span class="line">377</span><br><span class="line">378</span><br><span class="line">379</span><br><span class="line">380</span><br><span class="line">381</span><br><span class="line">382</span><br><span class="line">383</span><br><span class="line">384</span><br><span class="line">385</span><br><span class="line">386</span><br><span class="line">387</span><br><span class="line">388</span><br><span class="line">389</span><br><span class="line">390</span><br><span class="line">391</span><br><span class="line">392</span><br><span class="line">393</span><br><span class="line">394</span><br><span class="line">395</span><br><span class="line">396</span><br><span class="line">397</span><br><span class="line">398</span><br><span class="line">399</span><br><span class="line">400</span><br><span class="line">401</span><br><span class="line">402</span><br><span class="line">403</span><br><span class="line">404</span><br><span class="line">405</span><br><span class="line">406</span><br><span class="line">407</span><br><span class="line">408</span><br><span class="line">409</span><br><span class="line">410</span><br><span class="line">411</span><br><span class="line">412</span><br><span class="line">413</span><br><span class="line">414</span><br><span class="line">415</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">/*</span></span><br><span class="line"><span class="comment"> * 文件名:SingleLinkList.h</span></span><br><span class="line"><span class="comment"> * 说明 ：类的各种声明</span></span><br><span class="line"><span class="comment"> */</span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">pragma</span> once <span class="comment">//VC编译器防止头文件被重复包含的一条预编译指令</span></span></span><br><span class="line"></span><br><span class="line"><span class="meta">#<span class="meta-keyword">define</span> status bool</span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">define</span> OK true</span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">define</span> ERROR false</span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">define</span> YES true</span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">define</span> NO false</span></span><br><span class="line"></span><br><span class="line"><span class="keyword">template</span> &lt;<span class="keyword">typename</span> DType&gt;</span><br><span class="line"><span class="class"><span class="keyword">class</span> <span class="title">Node</span></span></span><br><span class="line"><span class="class">&#123;</span></span><br><span class="line"><span class="keyword">public</span>:</span><br><span class="line">	DType data;</span><br><span class="line">	Node * pnext;</span><br><span class="line">&#125;;</span><br><span class="line"></span><br><span class="line"><span class="keyword">template</span> &lt;<span class="keyword">typename</span> DType&gt;</span><br><span class="line"><span class="class"><span class="keyword">class</span> <span class="title">CSingleLinkList</span></span></span><br><span class="line"><span class="class">&#123;</span></span><br><span class="line"><span class="keyword">private</span>:</span><br><span class="line">	Node&lt;DType&gt; *phead; <span class="comment">//链表头指针</span></span><br><span class="line"><span class="keyword">public</span>:</span><br><span class="line">	CSingleLinkList();<span class="comment">//构造，类被创建时调用</span></span><br><span class="line">	~CSingleLinkList();<span class="comment">//析构，类被销毁时调用</span></span><br><span class="line"><span class="keyword">public</span>:</span><br><span class="line">	<span class="comment">//初始化链表</span></span><br><span class="line">	<span class="function">status <span class="title">InitSList</span><span class="params">()</span></span>;</span><br><span class="line">	<span class="comment">//获取链表长度</span></span><br><span class="line">	<span class="function"><span class="keyword">int</span> <span class="title">GetSListLength</span><span class="params">()</span></span>;</span><br><span class="line">	<span class="comment">//增加一个节点 前插法</span></span><br><span class="line">	<span class="function">status <span class="title">AddSListNodeFront</span><span class="params">(DType idata)</span></span>;</span><br><span class="line">	<span class="comment">//增加一个节点 后插法</span></span><br><span class="line">	<span class="function">status <span class="title">AddSListNodeBack</span><span class="params">( DType idata)</span></span>;</span><br><span class="line">	<span class="comment">//判断链表是否为空</span></span><br><span class="line">	<span class="function">status <span class="title">IsSListEmpty</span><span class="params">()</span></span>;</span><br><span class="line">	<span class="comment">//获取指定位置节点值(注意，本程序规定0号为头节点，e获取删除元素)</span></span><br><span class="line">	<span class="function">status <span class="title">GetSListIndexNode</span><span class="params">(DType *e, <span class="keyword">int</span> index)</span></span>;</span><br><span class="line">	<span class="comment">//删除指定位置节点(e获取删除元素)</span></span><br><span class="line">	<span class="function">status <span class="title">DeleteSListIndexNode</span><span class="params">(DType *e, <span class="keyword">int</span> index)</span></span>;</span><br><span class="line">	<span class="comment">//查找链表中指定值(pindex获取位置0==&gt;not found)</span></span><br><span class="line">	<span class="function">status <span class="title">SearchSListNode</span><span class="params">(DType SData, <span class="keyword">int</span> *pindex)</span></span>;</span><br><span class="line">	<span class="comment">//指定位置前插</span></span><br><span class="line">	<span class="function">status <span class="title">InsertSListNodeFront</span><span class="params">(DType IData, <span class="keyword">int</span> index)</span></span>;</span><br><span class="line">	<span class="comment">//指定位置后插</span></span><br><span class="line">	<span class="function">status <span class="title">InsertSListNodeBack</span><span class="params">(DType IData, <span class="keyword">int</span> index)</span></span>;</span><br><span class="line">	<span class="comment">//清空链表(保留根节点)</span></span><br><span class="line">	<span class="function">status <span class="title">ClearSList</span><span class="params">()</span></span>;</span><br><span class="line">	<span class="comment">//销毁链表(all delete)</span></span><br><span class="line">	<span class="function">status <span class="title">DestorySList</span><span class="params">()</span></span>;</span><br><span class="line">	<span class="comment">//尾部删除一个元素</span></span><br><span class="line">	<span class="function">status <span class="title">DeleteSListNodeBack</span><span class="params">()</span></span>;</span><br><span class="line">	<span class="comment">//打印链表   此函数根据实际情况而定</span></span><br><span class="line">	<span class="function"><span class="keyword">void</span> <span class="title">PrintSList</span><span class="params">()</span></span>;</span><br><span class="line">&#125;;</span><br><span class="line"></span><br><span class="line"><span class="comment">/*</span></span><br><span class="line"><span class="comment"> * 文件名:SingleLinkList.cpp</span></span><br><span class="line"><span class="comment"> * 说明 ：类的各种方法的实现</span></span><br><span class="line"><span class="comment"> */</span></span><br><span class="line"></span><br><span class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string">"SingleLinkList.h"</span></span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string">&lt;stdio.h&gt;</span></span></span><br><span class="line"></span><br><span class="line"><span class="keyword">template</span> &lt;<span class="keyword">typename</span> DType&gt;</span><br><span class="line">CSingleLinkList&lt;DType&gt;::CSingleLinkList()</span><br><span class="line">&#123;</span><br><span class="line">	<span class="built_in">cout</span> &lt;&lt; <span class="string">"链表创建"</span> &lt;&lt; <span class="built_in">endl</span>;</span><br><span class="line">	InitSList();</span><br><span class="line">&#125;</span><br><span class="line"><span class="keyword">template</span> &lt;<span class="keyword">typename</span> DType&gt;</span><br><span class="line">CSingleLinkList&lt;DType&gt;::~CSingleLinkList()</span><br><span class="line">&#123;</span><br><span class="line">	<span class="built_in">cout</span> &lt;&lt; <span class="string">"链表销毁"</span> &lt;&lt; <span class="built_in">endl</span>;</span><br><span class="line">	DestorySList();</span><br><span class="line">&#125;</span><br><span class="line"><span class="comment">//初始化链表</span></span><br><span class="line"><span class="keyword">template</span> &lt;<span class="keyword">typename</span> DType&gt;</span><br><span class="line">status CSingleLinkList&lt;DType&gt;::InitSList()</span><br><span class="line">&#123;</span><br><span class="line">	Node&lt;DType&gt; * ph = <span class="keyword">new</span> Node&lt;DType&gt;;</span><br><span class="line">	<span class="keyword">if</span> (ph != <span class="literal">NULL</span>)</span><br><span class="line">	&#123;</span><br><span class="line">		ph-&gt;pnext = <span class="literal">nullptr</span>;</span><br><span class="line">		<span class="keyword">this</span>-&gt;phead = ph; <span class="comment">//头结点</span></span><br><span class="line">		<span class="keyword">return</span> OK;</span><br><span class="line">	&#125;</span><br><span class="line">	<span class="keyword">return</span> ERROR;</span><br><span class="line">&#125;</span><br><span class="line"><span class="comment">//获取链表长度(head_node is not included)</span></span><br><span class="line"><span class="keyword">template</span> &lt;<span class="keyword">typename</span> DType&gt;</span><br><span class="line"><span class="keyword">int</span> CSingleLinkList&lt;DType&gt;::GetSListLength()</span><br><span class="line">&#123;</span><br><span class="line">	<span class="keyword">int</span> length = <span class="number">0</span>;</span><br><span class="line">	Node&lt;DType&gt; * phead = <span class="keyword">this</span>-&gt;phead;</span><br><span class="line">	<span class="keyword">while</span> (phead-&gt;pnext != <span class="literal">nullptr</span>)</span><br><span class="line">	&#123;</span><br><span class="line">		length++;</span><br><span class="line">		phead = phead-&gt;pnext;</span><br><span class="line">	&#125;</span><br><span class="line">	<span class="keyword">return</span> length;</span><br><span class="line">&#125;</span><br><span class="line"><span class="comment">//增加一个节点 前插法</span></span><br><span class="line"><span class="keyword">template</span> &lt;<span class="keyword">typename</span> DType&gt;</span><br><span class="line">status CSingleLinkList&lt;DType&gt;::AddSListNodeFront( DType idata)</span><br><span class="line">&#123;</span><br><span class="line">	Node&lt;DType&gt; * pnode = <span class="keyword">new</span> Node&lt;DType&gt;;</span><br><span class="line">	<span class="keyword">if</span> (pnode != <span class="literal">NULL</span>)</span><br><span class="line">	&#123;</span><br><span class="line">		pnode-&gt;data = idata;</span><br><span class="line">		pnode-&gt;pnext = <span class="keyword">this</span>-&gt;phead-&gt;pnext;</span><br><span class="line">		<span class="keyword">this</span>-&gt;phead-&gt;pnext = pnode; <span class="comment">//挂载</span></span><br><span class="line">		</span><br><span class="line">		<span class="comment">//printf("pnode = %p  pnode-&gt;pnext = %p this-&gt;phead-&gt;pnext = %p this-&gt;phead = %p\n", pnode, pnode-&gt;pnext, this-&gt;phead-&gt;pnext, this-&gt;phead);</span></span><br><span class="line">		<span class="keyword">return</span> OK;</span><br><span class="line">	&#125;</span><br><span class="line">	<span class="keyword">return</span> ERROR;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"></span><br><span class="line"><span class="comment">//增加一个节点 尾插法</span></span><br><span class="line"><span class="keyword">template</span> &lt;<span class="keyword">typename</span> DType&gt;</span><br><span class="line">status CSingleLinkList&lt;DType&gt;::AddSListNodeBack(DType idata)</span><br><span class="line">&#123;</span><br><span class="line">	Node&lt;DType&gt; * pnode = <span class="keyword">new</span> Node&lt;DType&gt;;</span><br><span class="line">	Node&lt;DType&gt; * phead = <span class="keyword">this</span>-&gt;phead;</span><br><span class="line">	<span class="keyword">if</span> (pnode != <span class="literal">NULL</span>)</span><br><span class="line">	&#123;</span><br><span class="line">		<span class="keyword">while</span> (phead-&gt;pnext != <span class="literal">nullptr</span>)</span><br><span class="line">		&#123;</span><br><span class="line">			phead = phead-&gt;pnext;</span><br><span class="line">		&#125;</span><br><span class="line">		pnode-&gt;data = idata;</span><br><span class="line">		pnode-&gt;pnext = <span class="literal">nullptr</span>;</span><br><span class="line">		phead-&gt;pnext = pnode; <span class="comment">//挂载</span></span><br><span class="line">		<span class="keyword">return</span> OK;</span><br><span class="line">	&#125;</span><br><span class="line">	<span class="keyword">return</span> ERROR;</span><br><span class="line">&#125;</span><br><span class="line"><span class="comment">//判断链表是否为空</span></span><br><span class="line"><span class="keyword">template</span> &lt;<span class="keyword">typename</span> DType&gt;</span><br><span class="line">status CSingleLinkList&lt;DType&gt;::IsSListEmpty()</span><br><span class="line">&#123;</span><br><span class="line">	<span class="keyword">if</span> (<span class="keyword">this</span>-&gt;phead-&gt;pnext == <span class="literal">nullptr</span>)</span><br><span class="line">	&#123;</span><br><span class="line">		<span class="keyword">return</span> YES;</span><br><span class="line">	&#125;</span><br><span class="line">	<span class="keyword">return</span> NO;</span><br><span class="line">&#125;</span><br><span class="line"><span class="comment">//获取指定位置节点值(注意，本程序规定0号为头节点，e获取节点的值)</span></span><br><span class="line"><span class="keyword">template</span> &lt;<span class="keyword">typename</span> DType&gt;</span><br><span class="line">status CSingleLinkList&lt;DType&gt;::GetSListIndexNode(DType *e, <span class="keyword">int</span> index)</span><br><span class="line">&#123;</span><br><span class="line">	Node&lt;DType&gt; * phead = <span class="keyword">this</span>-&gt;phead;</span><br><span class="line">	<span class="keyword">int</span> i = <span class="number">0</span>; <span class="comment">//计数器</span></span><br><span class="line">	<span class="keyword">if</span> (phead-&gt;pnext == <span class="literal">nullptr</span> || index &lt; <span class="number">1</span> || index &gt; GetSListLength())</span><br><span class="line">	&#123;</span><br><span class="line">		<span class="keyword">return</span> ERROR; <span class="comment">//异常 处理</span></span><br><span class="line">	&#125;</span><br><span class="line">	<span class="keyword">while</span> (phead-&gt;pnext != <span class="literal">nullptr</span>)</span><br><span class="line">	&#123;</span><br><span class="line">		i++;</span><br><span class="line">		phead = phead-&gt;pnext;</span><br><span class="line">		<span class="keyword">if</span> (i == index)</span><br><span class="line">		&#123;</span><br><span class="line">			*e = phead-&gt;data;</span><br><span class="line">			<span class="keyword">return</span> OK;</span><br><span class="line">		&#125;</span><br><span class="line">	&#125;</span><br><span class="line">	<span class="keyword">return</span> ERROR;</span><br><span class="line">&#125;</span><br><span class="line"><span class="comment">//删除指定位置节点(e获取删除元素)</span></span><br><span class="line"><span class="keyword">template</span> &lt;<span class="keyword">typename</span> DType&gt;</span><br><span class="line">status CSingleLinkList&lt;DType&gt;::DeleteSListIndexNode( DType *e, <span class="keyword">int</span> index)</span><br><span class="line">&#123;</span><br><span class="line">	Node&lt;DType&gt; * phead = <span class="keyword">this</span>-&gt;phead;</span><br><span class="line">	<span class="keyword">int</span> i = <span class="number">0</span>; <span class="comment">//计数器</span></span><br><span class="line">	Node&lt;DType&gt; * q = <span class="literal">nullptr</span>;</span><br><span class="line">	<span class="keyword">if</span> (phead-&gt;pnext == <span class="literal">nullptr</span> || index &lt; <span class="number">1</span> || index &gt; GetSListLength())</span><br><span class="line">	&#123;</span><br><span class="line">		<span class="keyword">return</span> ERROR; <span class="comment">//异常 处理</span></span><br><span class="line">	&#125;</span><br><span class="line">	<span class="keyword">while</span> (phead-&gt;pnext != <span class="literal">nullptr</span>)</span><br><span class="line">	&#123;</span><br><span class="line">		i++;</span><br><span class="line">		q = phead; <span class="comment">//保存备用</span></span><br><span class="line">		phead = phead-&gt;pnext;</span><br><span class="line">		<span class="keyword">if</span> (i == index)</span><br><span class="line">		&#123;</span><br><span class="line">			*e = phead-&gt;data;</span><br><span class="line">			q-&gt;pnext = phead-&gt;pnext; <span class="comment">//删除出局</span></span><br><span class="line">			<span class="keyword">return</span> OK;</span><br><span class="line">		&#125;</span><br><span class="line">	&#125;</span><br><span class="line">	<span class="keyword">return</span> ERROR;</span><br><span class="line">&#125;</span><br><span class="line"><span class="comment">//查找链表中指定值(pindex获取位置   0==&gt;not found)</span></span><br><span class="line"><span class="keyword">template</span> &lt;<span class="keyword">typename</span> DType&gt;</span><br><span class="line">status CSingleLinkList&lt;DType&gt;::SearchSListNode( DType SData, <span class="keyword">int</span> *pindex)</span><br><span class="line">&#123;</span><br><span class="line">	Node&lt;DType&gt; * phead = <span class="keyword">this</span>-&gt;phead;</span><br><span class="line">	<span class="keyword">int</span> iCount = <span class="number">0</span>;<span class="comment">//计数器</span></span><br><span class="line">	<span class="keyword">while</span> (phead-&gt;pnext != <span class="literal">nullptr</span>)</span><br><span class="line">	&#123;</span><br><span class="line">		iCount++;</span><br><span class="line">		phead = phead-&gt;pnext;</span><br><span class="line">		<span class="keyword">if</span> (phead-&gt;data == SData)</span><br><span class="line">		&#123;</span><br><span class="line">			*pindex = iCount;</span><br><span class="line">			<span class="keyword">return</span> YES;</span><br><span class="line">		&#125;</span><br><span class="line">	&#125;</span><br><span class="line">	*pindex = <span class="number">0</span>;</span><br><span class="line">	<span class="keyword">return</span> NO;</span><br><span class="line">&#125;</span><br><span class="line"><span class="comment">//指定位置前插</span></span><br><span class="line"><span class="keyword">template</span> &lt;<span class="keyword">typename</span> DType&gt;</span><br><span class="line">status CSingleLinkList&lt;DType&gt;::InsertSListNodeFront(DType IData, <span class="keyword">int</span> index)</span><br><span class="line">&#123;</span><br><span class="line">	Node&lt;DType&gt; * phead = <span class="keyword">this</span>-&gt;phead;</span><br><span class="line">	<span class="keyword">if</span> (phead-&gt;pnext == <span class="literal">nullptr</span> || index &lt; <span class="number">1</span> || index &gt; GetSListLength())</span><br><span class="line">	&#123;</span><br><span class="line">		<span class="keyword">return</span> ERROR; <span class="comment">//异常 处理</span></span><br><span class="line">	&#125;</span><br><span class="line">	<span class="keyword">int</span> iCount = <span class="number">0</span>; <span class="comment">//计数器</span></span><br><span class="line">	Node&lt;DType&gt; * q = <span class="literal">nullptr</span>; <span class="comment">//备用</span></span><br><span class="line">	<span class="keyword">while</span> (phead-&gt;pnext != <span class="literal">nullptr</span>)</span><br><span class="line">	&#123;</span><br><span class="line">		iCount++;</span><br><span class="line">		q = phead;</span><br><span class="line">		phead = phead-&gt;pnext;</span><br><span class="line">		<span class="keyword">if</span> ( iCount == index )</span><br><span class="line">		&#123;</span><br><span class="line">			Node&lt;DType&gt; * p = <span class="keyword">new</span> Node&lt;DType&gt;;</span><br><span class="line">			p-&gt;data = IData;</span><br><span class="line">			p-&gt;pnext = phead;</span><br><span class="line">			q-&gt;pnext = p;   <span class="comment">//前插</span></span><br><span class="line">			<span class="keyword">return</span> OK;</span><br><span class="line">		&#125;</span><br><span class="line">	&#125;</span><br><span class="line">	<span class="keyword">return</span> ERROR;</span><br><span class="line">&#125;</span><br><span class="line"><span class="comment">//指定位置后插</span></span><br><span class="line"><span class="keyword">template</span> &lt;<span class="keyword">typename</span> DType&gt;</span><br><span class="line">status CSingleLinkList&lt;DType&gt;::InsertSListNodeBack( DType IData, <span class="keyword">int</span> index)</span><br><span class="line">&#123;</span><br><span class="line">	Node&lt;DType&gt; * phead = <span class="keyword">this</span>-&gt;phead;</span><br><span class="line">	<span class="keyword">if</span> (phead-&gt;pnext == <span class="literal">nullptr</span> || index &lt; <span class="number">1</span> || index &gt; GetSListLength())</span><br><span class="line">	&#123;</span><br><span class="line">		<span class="keyword">return</span> ERROR; <span class="comment">//异常 处理</span></span><br><span class="line">	&#125;</span><br><span class="line">	<span class="keyword">int</span> iCount = <span class="number">0</span>; <span class="comment">//计数器</span></span><br><span class="line">	Node&lt;DType&gt; * q = <span class="literal">nullptr</span>; <span class="comment">//备用</span></span><br><span class="line">	<span class="keyword">while</span> (phead-&gt;pnext != <span class="literal">nullptr</span>)</span><br><span class="line">	&#123;</span><br><span class="line">		iCount++;</span><br><span class="line">		q = phead;</span><br><span class="line">		phead = phead-&gt;pnext;</span><br><span class="line">		<span class="keyword">if</span> (iCount == index)</span><br><span class="line">		&#123;</span><br><span class="line">			Node&lt;DType&gt; * p = <span class="keyword">new</span> Node&lt;DType&gt;;</span><br><span class="line">			q = phead;</span><br><span class="line">			phead = phead-&gt;pnext; <span class="comment">//后插就是后一个节点的前插咯</span></span><br><span class="line">			p-&gt;data = IData;</span><br><span class="line">			p-&gt;pnext = phead;</span><br><span class="line">			q-&gt;pnext = p;   </span><br><span class="line">			<span class="keyword">return</span> OK;</span><br><span class="line">		&#125;</span><br><span class="line">	&#125;</span><br><span class="line">	<span class="keyword">return</span> ERROR;</span><br><span class="line">&#125;</span><br><span class="line"><span class="comment">//清空链表(保留根节点)</span></span><br><span class="line"><span class="keyword">template</span> &lt;<span class="keyword">typename</span> DType&gt;</span><br><span class="line">status CSingleLinkList&lt;DType&gt;::ClearSList()</span><br><span class="line">&#123;</span><br><span class="line">	Node&lt;DType&gt; * phead = <span class="keyword">this</span>-&gt;phead;</span><br><span class="line">	Node&lt;DType&gt; * q = <span class="literal">nullptr</span>; <span class="comment">//防止那啥，野指针</span></span><br><span class="line">	phead = phead-&gt;pnext;<span class="comment">//保留头节点</span></span><br><span class="line">	<span class="keyword">while</span> (phead != <span class="literal">nullptr</span>)</span><br><span class="line">	&#123;</span><br><span class="line">		q = phead;</span><br><span class="line">		phead = phead-&gt;pnext;</span><br><span class="line">		<span class="keyword">delete</span> q; <span class="comment">//释放</span></span><br><span class="line">	&#125;</span><br><span class="line">	<span class="keyword">this</span>-&gt;phead-&gt;pnext = <span class="literal">nullptr</span>;</span><br><span class="line">	<span class="keyword">return</span> OK;</span><br><span class="line">&#125;</span><br><span class="line"><span class="comment">//销毁链表(all delete)</span></span><br><span class="line"><span class="keyword">template</span> &lt;<span class="keyword">typename</span> DType&gt;</span><br><span class="line">status CSingleLinkList&lt;DType&gt;::DestorySList()</span><br><span class="line">&#123;</span><br><span class="line">	ClearSList();</span><br><span class="line">	<span class="keyword">delete</span> <span class="keyword">this</span>-&gt;phead;<span class="comment">//释放头结点 </span></span><br><span class="line">	<span class="keyword">return</span> OK;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="keyword">template</span> &lt;<span class="keyword">typename</span> DType&gt;</span><br><span class="line">status CSingleLinkList&lt;DType&gt;::DeleteSListNodeBack()</span><br><span class="line">&#123;</span><br><span class="line">	Node&lt;DType&gt; * phead = <span class="keyword">this</span>-&gt;phead;</span><br><span class="line">	Node&lt;DType&gt; * q = <span class="literal">nullptr</span>; <span class="comment">//备用</span></span><br><span class="line">	<span class="keyword">if</span> (phead-&gt;pnext == <span class="literal">nullptr</span>)</span><br><span class="line">	&#123;</span><br><span class="line">		<span class="keyword">return</span> ERROR; <span class="comment">//链表都空了还删鸡毛</span></span><br><span class="line">	&#125;</span><br><span class="line">	<span class="keyword">while</span> (phead-&gt;pnext != <span class="literal">nullptr</span>)</span><br><span class="line">	&#123;</span><br><span class="line">		q = phead;</span><br><span class="line">		phead = phead-&gt;pnext;</span><br><span class="line">	&#125;</span><br><span class="line">	q-&gt;pnext = <span class="literal">nullptr</span>;</span><br><span class="line">	<span class="keyword">delete</span> phead;</span><br><span class="line"></span><br><span class="line">	<span class="keyword">return</span> OK;</span><br><span class="line">	</span><br><span class="line">&#125;</span><br><span class="line"><span class="keyword">template</span> &lt;<span class="keyword">typename</span> DType&gt;</span><br><span class="line"><span class="keyword">void</span> CSingleLinkList&lt;DType&gt;::PrintSList()</span><br><span class="line">&#123;</span><br><span class="line">	Node&lt;DType&gt; * phead = <span class="keyword">this</span>-&gt;phead;</span><br><span class="line">	<span class="keyword">if</span> (phead-&gt;pnext == <span class="literal">nullptr</span> || phead == <span class="literal">nullptr</span>)</span><br><span class="line">	&#123;</span><br><span class="line">		<span class="built_in">cout</span> &lt;&lt; <span class="string">"链表为空，打印鸡毛"</span> &lt;&lt; <span class="built_in">endl</span>;</span><br><span class="line">		<span class="keyword">return</span>;</span><br><span class="line">	&#125;</span><br><span class="line">	<span class="keyword">int</span> i = <span class="number">1</span>;</span><br><span class="line">	<span class="built_in">cout</span> &lt;&lt; <span class="string">"===============print list================"</span> &lt;&lt; <span class="built_in">endl</span>;</span><br><span class="line">	<span class="keyword">while</span> (phead-&gt;pnext != <span class="literal">nullptr</span>)</span><br><span class="line">	&#123;</span><br><span class="line">		phead = phead-&gt;pnext;</span><br><span class="line">		<span class="built_in">cout</span> &lt;&lt;<span class="string">"node["</span> &lt;&lt; i++ &lt;&lt; <span class="string">"] = "</span> &lt;&lt; phead-&gt;data&lt;&lt;<span class="built_in">endl</span>;</span><br><span class="line">	&#125;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="comment">/*</span></span><br><span class="line"><span class="comment"> * 文件名:SingleLinkListTest.cpp</span></span><br><span class="line"><span class="comment"> * 说明 ：测试代码</span></span><br><span class="line"><span class="comment"> */</span></span><br><span class="line"></span><br><span class="line"> <span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string">&lt;iostream&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string">"SingleLinkList.h"</span></span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string">"SingleLinkList.cpp"</span></span></span><br><span class="line"></span><br><span class="line"><span class="keyword">using</span> <span class="keyword">namespace</span> <span class="built_in">std</span>;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">main</span><span class="params">()</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">	CSingleLinkList&lt;<span class="keyword">int</span>&gt; * pMySList = <span class="keyword">new</span> CSingleLinkList&lt;<span class="keyword">int</span>&gt;;</span><br><span class="line">	<span class="built_in">cout</span> &lt;&lt; pMySList-&gt;IsSListEmpty() &lt;&lt; <span class="built_in">endl</span>;</span><br><span class="line">	pMySList-&gt;AddSListNodeFront(<span class="number">111</span>);</span><br><span class="line">	pMySList-&gt;AddSListNodeFront(<span class="number">222</span>);</span><br><span class="line">	pMySList-&gt;AddSListNodeFront(<span class="number">333</span>);</span><br><span class="line"></span><br><span class="line">	<span class="built_in">cout</span> &lt;&lt; <span class="string">"链表长度"</span> &lt;&lt; pMySList-&gt;GetSListLength() &lt;&lt; <span class="built_in">endl</span>;</span><br><span class="line"></span><br><span class="line">	pMySList-&gt;PrintSList();</span><br><span class="line"></span><br><span class="line">	pMySList-&gt;AddSListNodeBack(<span class="number">444</span>);</span><br><span class="line">	pMySList-&gt;AddSListNodeBack(<span class="number">555</span>);</span><br><span class="line">	pMySList-&gt;AddSListNodeBack(<span class="number">666</span>);</span><br><span class="line"></span><br><span class="line">	pMySList-&gt;PrintSList();</span><br><span class="line"></span><br><span class="line">	<span class="built_in">cout</span> &lt;&lt; pMySList-&gt;IsSListEmpty() &lt;&lt; <span class="built_in">endl</span>;</span><br><span class="line">	<span class="built_in">cout</span> &lt;&lt; <span class="string">"链表长度"</span> &lt;&lt; pMySList-&gt;GetSListLength() &lt;&lt; <span class="built_in">endl</span>;</span><br><span class="line"></span><br><span class="line">	<span class="keyword">int</span> GetElem, GetIndex;</span><br><span class="line">	pMySList-&gt;GetSListIndexNode(&amp;GetElem, <span class="number">2</span>);</span><br><span class="line">	<span class="built_in">cout</span> &lt;&lt; <span class="string">"Got Elem = "</span> &lt;&lt; GetElem &lt;&lt; <span class="built_in">endl</span>;</span><br><span class="line"></span><br><span class="line">	pMySList-&gt;GetSListIndexNode(&amp;GetElem, <span class="number">6</span>);</span><br><span class="line">	<span class="built_in">cout</span> &lt;&lt; <span class="string">"Got Elem = "</span> &lt;&lt; GetElem &lt;&lt; <span class="built_in">endl</span>;</span><br><span class="line"></span><br><span class="line">	pMySList-&gt;GetSListIndexNode(&amp;GetElem, <span class="number">4</span>);</span><br><span class="line">	<span class="built_in">cout</span> &lt;&lt; <span class="string">"Got Elem = "</span> &lt;&lt; GetElem &lt;&lt; <span class="built_in">endl</span>;</span><br><span class="line"></span><br><span class="line">	pMySList-&gt;DeleteSListIndexNode(&amp;GetElem, <span class="number">1</span>);</span><br><span class="line">	<span class="built_in">cout</span> &lt;&lt; <span class="string">"del Elem = "</span> &lt;&lt; GetElem &lt;&lt; <span class="built_in">endl</span>;</span><br><span class="line">	pMySList-&gt;DeleteSListIndexNode(&amp;GetElem, <span class="number">3</span>);</span><br><span class="line">	<span class="built_in">cout</span> &lt;&lt; <span class="string">"del Elem = "</span> &lt;&lt; GetElem &lt;&lt; <span class="built_in">endl</span>;</span><br><span class="line">	</span><br><span class="line"></span><br><span class="line">	pMySList-&gt;PrintSList();</span><br><span class="line"></span><br><span class="line">	pMySList-&gt;SearchSListNode(<span class="number">555</span>, &amp;GetIndex);</span><br><span class="line">	<span class="built_in">cout</span> &lt;&lt; <span class="string">"Search Index = "</span> &lt;&lt; GetIndex &lt;&lt; <span class="built_in">endl</span>;</span><br><span class="line">	pMySList-&gt;SearchSListNode(<span class="number">111</span>, &amp;GetIndex);</span><br><span class="line">	<span class="built_in">cout</span> &lt;&lt; <span class="string">"Search Index = "</span> &lt;&lt; GetIndex &lt;&lt; <span class="built_in">endl</span>;</span><br><span class="line">	pMySList-&gt;SearchSListNode(<span class="number">666</span>, &amp;GetIndex);</span><br><span class="line">	<span class="built_in">cout</span> &lt;&lt; <span class="string">"Search Index = "</span> &lt;&lt; GetIndex &lt;&lt; <span class="built_in">endl</span>;</span><br><span class="line"></span><br><span class="line">	pMySList-&gt;InsertSListNodeFront(<span class="number">333</span>, <span class="number">1</span>);</span><br><span class="line">	pMySList-&gt;InsertSListNodeFront(<span class="number">444</span>, <span class="number">4</span>);</span><br><span class="line"></span><br><span class="line">	pMySList-&gt;PrintSList();</span><br><span class="line"></span><br><span class="line">	pMySList-&gt;InsertSListNodeBack(<span class="number">777</span>, <span class="number">3</span>);</span><br><span class="line">	pMySList-&gt;InsertSListNodeBack(<span class="number">888</span>, <span class="number">5</span>);</span><br><span class="line"></span><br><span class="line">	pMySList-&gt;PrintSList();</span><br><span class="line"></span><br><span class="line">	pMySList-&gt;DeleteSListNodeBack();</span><br><span class="line">	pMySList-&gt;PrintSList();</span><br><span class="line">	pMySList-&gt;DeleteSListNodeBack();</span><br><span class="line">	pMySList-&gt;PrintSList();</span><br><span class="line">	pMySList-&gt;DeleteSListNodeBack();</span><br><span class="line">	pMySList-&gt;PrintSList();</span><br><span class="line"></span><br><span class="line">	<span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line">代码如果有不正确的地方，欢迎大家来指正哈。</span><br></pre></td></tr></table></figure></p>
<h2 id="04-静态链表-circular-linked-list"><a href="#04-静态链表-circular-linked-list" class="headerlink" title="04 静态链表(circular linked list)"></a>04 静态链表(circular linked list)</h2><h3 id="4-1-什么是静态链表？"><a href="#4-1-什么是静态链表？" class="headerlink" title="4.1 什么是静态链表？"></a>4.1 什么是静态链表？</h3><p>我们把线性表的元素存放在数组中，这些元素由两个域组成：</p>
<ul>
<li>数据域data</li>
<li>指针域cur</li>
</ul>
<p>数据域是存放数据的，而指针域，这里和链表不同是，它存的不再是指向下一个节点的内存地址。而是下一个节点在数组中的下标。我们就把这种用数组描述的链表称为静态表，该方法也称之为游标实现法。如下图所示：<br><img src="http://upload-images.jianshu.io/upload_images/10386940-66b8deab6693fddd.png?imageMogr2/auto-orient/strip%7CimageView2/2/w/1240" alt=""></p>
<p>由上图我们需要注意以下几点：</p>
<ul>
<li>我们对数组的第一个元素和最后一个元素做特殊处理，不存放数据。</li>
<li>把未使用的数组元素称为备用链表。</li>
<li>数组的第一个元素(下标为0)的cur域存放备用链表第一个节点的下标。</li>
<li>数组的最后一个元素的cur域存放第一个有数据的节点的下标，相当于链表中头结点的存在。链表为空时，其值为0。</li>
</ul>
<p>如下图：</p>
<p><img src="http://upload-images.jianshu.io/upload_images/10386940-fdfdfdad92a5417f.png?imageMogr2/auto-orient/strip%7CimageView2/2/w/1240" alt=""></p>
<p>引出的问题：数组的长度定义的问题，无法预支。所以，为了防止溢出，我们一般将静态表开得大一点。</p>
<h3 id="4-2-静态链表存储的代码描述"><a href="#4-2-静态链表存储的代码描述" class="headerlink" title="4.2 静态链表存储的代码描述"></a>4.2 静态链表存储的代码描述</h3><p>基于上面的讲解，我们来看看代码是怎么描述这种存储结构的。<br><figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">//---------线性表的静态单链表存储结构--------</span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">define</span> MAXSIZE 1000 <span class="comment">/*假设链表最大长度为1000*/</span></span></span><br><span class="line"><span class="keyword">typedef</span> <span class="class"><span class="keyword">struct</span></span></span><br><span class="line"><span class="class">&#123;</span></span><br><span class="line">    datatype data;</span><br><span class="line">    <span class="keyword">int</span> cur;   <span class="comment">//为0时表示无指向</span></span><br><span class="line">&#125;SLinkList[MAXSIZE];</span><br></pre></td></tr></table></figure></p>
<p>接下来我们讲解几个重要的操作实现。</p>
<h3 id="4-3-静态链表的插入操作"><a href="#4-3-静态链表的插入操作" class="headerlink" title="4.3 静态链表的插入操作"></a>4.3 静态链表的插入操作</h3><p>前面我们讲动态链表的时候说过，增加和删除一个节点我们可以用malloc()和free()函数(C++可用new和delete)来实现。但是现在由于我们操作的是静态表，它可是用数组存的，可没有这种操作了。因此我们首先来自己实现一个静态表的malloc和free。</p>
<p>那么怎么辨别数组中哪些空间没有被使用呢？一个好的解决办法是，将所有未使用或者被删除的空间串成一个备用链表。插入节点时便可以从备用链表获取第一个未使用的空间的下标。因此我们在初始化的时候会做这样的工作：</p>
<figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">SListInit</span><span class="params">(SLinkList space)</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    <span class="keyword">int</span> i;</span><br><span class="line">    <span class="keyword">for</span>(i = <span class="number">0</span>; i &lt; MAXSIZE; i++)</span><br><span class="line">        space[i].cur = i+<span class="number">1</span>; <span class="comment">//将所有结点链入备用链表</span></span><br><span class="line">    <span class="comment">//备用链表头指针链像第二个结点</span></span><br><span class="line">    space[<span class="number">0</span>].cur = space[<span class="number">1</span>].cur; </span><br><span class="line">    <span class="comment">//第一个结点作为链表的头结点  </span></span><br><span class="line">    space[<span class="number">1</span>].cur = <span class="number">0</span>;              </span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p><strong>分配内存</strong><br><figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br></pre></td><td class="code"><pre><span class="line">/分配备用链表的一个结点,返回下标</span><br><span class="line"><span class="comment">//若为0，则说明备用链表用完</span></span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">Malloc_SL</span><span class="params">(SLinkList space)</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    <span class="keyword">int</span> i = space[<span class="number">0</span>].cur;</span><br><span class="line">    <span class="comment">//判断备用链表是否非空</span></span><br><span class="line">    <span class="keyword">if</span>(space[<span class="number">0</span>].cur)    </span><br><span class="line">        <span class="comment">//备用链表头指针指向第二个空结点</span></span><br><span class="line">        space[<span class="number">0</span>].cur = space[i].cur; </span><br><span class="line"></span><br><span class="line">    <span class="keyword">return</span> i;    <span class="comment">//返回第一个空结点</span></span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure></p>
<p>上面的代码应该是没有难度的。写完了这个函数，我们来看看静态表中具体如何插入：<br><figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">//在链表的第i个位置插入元素e</span></span><br><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">SlistInsert</span><span class="params">(SLinkList space, <span class="keyword">int</span> i, ElemType e)</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    <span class="comment">//超出范围</span></span><br><span class="line">    <span class="keyword">if</span>(i &lt; <span class="number">1</span> || i &gt; SListLength(space)+<span class="number">1</span>) </span><br><span class="line">        <span class="keyword">return</span>;</span><br><span class="line">    <span class="keyword">int</span> k = <span class="number">1</span>, j;</span><br><span class="line">    <span class="comment">//使k指示要插入的结点的前一个结点</span></span><br><span class="line">    <span class="keyword">for</span>(j = <span class="number">0</span>; j &lt;i<span class="number">-1</span>; j++) </span><br><span class="line">        k = space[k].cur;</span><br><span class="line"></span><br><span class="line">    <span class="keyword">int</span> v = Malloc_SL(space);</span><br><span class="line">    <span class="keyword">if</span>(v)     <span class="comment">//如果有空间</span></span><br><span class="line">    &#123;</span><br><span class="line">        space[v].data = e;</span><br><span class="line">        space[v].cur = space[k].cur;</span><br><span class="line">        space[k].cur = v;  <span class="comment">//链入链表</span></span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure></p>
<p>注意几点：</p>
<ul>
<li>首先我们让k指向了要插入节点(记为X)的前一个位置(记为Y节点)，前插法。</li>
<li>然后我们在静态表内申请空间，存放新的节点(记为N)。</li>
<li>把数据放进新申请的节点里面。</li>
<li>新节点N的cur域指向X节点，然后让Y节点指向N节点。</li>
</ul>
<p>该过程不难理解。就不上图了……</p>
<h3 id="4-4-静态链表的删除操作"><a href="#4-4-静态链表的删除操作" class="headerlink" title="4.4 静态链表的删除操作"></a>4.4 静态链表的删除操作</h3><p>删除同样需要自己实现free函数，我们来看看代码：</p>
<p><strong>回收内存</strong><br><figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">//将下标为k的空闲结点回收到备用链表</span></span><br><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">Free_SL</span><span class="params">(SLinkList space, <span class="keyword">int</span> k)</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    <span class="comment">//将备用链表链到k之后</span></span><br><span class="line">    space[k].cur = space[<span class="number">0</span>].cur;  </span><br><span class="line">    <span class="comment">//将k链到备用链表头之后</span></span><br><span class="line">    space[<span class="number">0</span>].cur = k;               </span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure></p>
<p>删除以后记得把空间重新挂载到备用链表上以便下一次使用。下面我们实现删除的代码：</p>
<figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">//删除第i个位置的元素</span></span><br><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">SListDelete</span><span class="params">(SLinkList space, <span class="keyword">int</span> i)</span></span></span><br><span class="line"><span class="function"></span>&#123;   <span class="comment">//超出范围退出</span></span><br><span class="line">    <span class="keyword">if</span>(i &lt; <span class="number">1</span> || i &gt; SListLength(space))  </span><br><span class="line">        <span class="keyword">return</span> ;</span><br><span class="line">    <span class="keyword">int</span> k = <span class="number">1</span>, j;</span><br><span class="line">     <span class="comment">//使k指示要删除的结点的前一个结点</span></span><br><span class="line">    <span class="keyword">for</span>(j = <span class="number">0</span>; j &lt;i<span class="number">-1</span>; j++)  </span><br><span class="line">        k = space[k].cur;</span><br><span class="line"></span><br><span class="line">    <span class="keyword">int</span> temp = space[k].cur;</span><br><span class="line">    space[k].cur = space[temp].cur;</span><br><span class="line">    Free_SL(space, temp);</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p>其实代码也很好理解了。假如X、Y、Z……等等排列，我们要删除Y。无非就是告诉X，你不要指向Y了，你直接指向Z，然后我们再把Y给free了。就直接变成了X、Z……简单吧。</p>
<h3 id="4-5-静态链表的完整代码"><a href="#4-5-静态链表的完整代码" class="headerlink" title="4.5 静态链表的完整代码"></a>4.5 静态链表的完整代码</h3><figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br><span class="line">62</span><br><span class="line">63</span><br><span class="line">64</span><br><span class="line">65</span><br><span class="line">66</span><br><span class="line">67</span><br><span class="line">68</span><br><span class="line">69</span><br><span class="line">70</span><br><span class="line">71</span><br><span class="line">72</span><br><span class="line">73</span><br><span class="line">74</span><br><span class="line">75</span><br><span class="line">76</span><br><span class="line">77</span><br><span class="line">78</span><br><span class="line">79</span><br><span class="line">80</span><br><span class="line">81</span><br><span class="line">82</span><br><span class="line">83</span><br><span class="line">84</span><br><span class="line">85</span><br><span class="line">86</span><br><span class="line">87</span><br><span class="line">88</span><br><span class="line">89</span><br><span class="line">90</span><br><span class="line">91</span><br><span class="line">92</span><br><span class="line">93</span><br><span class="line">94</span><br><span class="line">95</span><br><span class="line">96</span><br><span class="line">97</span><br><span class="line">98</span><br><span class="line">99</span><br><span class="line">100</span><br><span class="line">101</span><br><span class="line">102</span><br><span class="line">103</span><br><span class="line">104</span><br><span class="line">105</span><br><span class="line">106</span><br><span class="line">107</span><br><span class="line">108</span><br><span class="line">109</span><br><span class="line">110</span><br><span class="line">111</span><br><span class="line">112</span><br><span class="line">113</span><br><span class="line">114</span><br><span class="line">115</span><br><span class="line">116</span><br><span class="line">117</span><br><span class="line">118</span><br><span class="line">119</span><br><span class="line">120</span><br><span class="line">121</span><br><span class="line">122</span><br><span class="line">123</span><br><span class="line">124</span><br><span class="line">125</span><br><span class="line">126</span><br><span class="line">127</span><br><span class="line">128</span><br><span class="line">129</span><br><span class="line">130</span><br><span class="line">131</span><br><span class="line">132</span><br><span class="line">133</span><br><span class="line">134</span><br><span class="line">135</span><br><span class="line">136</span><br><span class="line">137</span><br><span class="line">138</span><br><span class="line">139</span><br><span class="line">140</span><br><span class="line">141</span><br><span class="line">142</span><br><span class="line">143</span><br><span class="line">144</span><br><span class="line">145</span><br><span class="line">146</span><br><span class="line">147</span><br><span class="line">148</span><br><span class="line">149</span><br><span class="line">150</span><br><span class="line">151</span><br><span class="line">152</span><br><span class="line">153</span><br><span class="line">154</span><br><span class="line">155</span><br><span class="line">156</span><br><span class="line">157</span><br><span class="line">158</span><br><span class="line">159</span><br><span class="line">160</span><br><span class="line">161</span><br><span class="line">162</span><br><span class="line">163</span><br><span class="line">164</span><br><span class="line">165</span><br><span class="line">166</span><br><span class="line">167</span><br><span class="line">168</span><br><span class="line">169</span><br><span class="line">170</span><br><span class="line">171</span><br><span class="line">172</span><br><span class="line">173</span><br><span class="line">174</span><br><span class="line">175</span><br><span class="line">176</span><br><span class="line">177</span><br><span class="line">178</span><br><span class="line">179</span><br><span class="line">180</span><br><span class="line">181</span><br><span class="line">182</span><br><span class="line">183</span><br><span class="line">184</span><br><span class="line">185</span><br><span class="line">186</span><br><span class="line">187</span><br><span class="line">188</span><br><span class="line">189</span><br><span class="line">190</span><br><span class="line">191</span><br><span class="line">192</span><br><span class="line">193</span><br><span class="line">194</span><br></pre></td><td class="code"><pre><span class="line"></span><br><span class="line"><span class="comment">/*************************************</span></span><br><span class="line"><span class="comment">                静态链表</span></span><br><span class="line"><span class="comment">数据结构：每个数组节点都有值和游标.</span></span><br><span class="line"><span class="comment">游标表示下一个节点，节点分为已用节点和备用节点</span></span><br><span class="line"><span class="comment">第一个节点和最后节点保留：</span></span><br><span class="line"><span class="comment">第一个节点游标表示备用节点起始位置</span></span><br><span class="line"><span class="comment">最后一个节点游标表示已用节点的起始位置</span></span><br><span class="line"><span class="comment">已用节点的最后一个元素的游标指向0，表示末尾。</span></span><br><span class="line"><span class="comment">*************************************/</span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string">&lt;stdio.h&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string">&lt;stdlib.h&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string">&lt;unistd.h&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string">&lt;time.h&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">define</span> ERROR 0</span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">define</span> OK 1</span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">define</span> MAX 100     <span class="comment">//声明数组的最大长度</span></span></span><br><span class="line"></span><br><span class="line"><span class="keyword">typedef</span> <span class="keyword">int</span> Status,ElemType;</span><br><span class="line"><span class="keyword">typedef</span> <span class="class"><span class="keyword">struct</span>&#123;</span></span><br><span class="line">   <span class="keyword">int</span> data;    <span class="comment">//数据</span></span><br><span class="line">   <span class="keyword">int</span> cur;     <span class="comment">//游标</span></span><br><span class="line">&#125;component,staticlink[MAX]; <span class="comment">//定义结构体数组</span></span><br><span class="line"></span><br><span class="line"><span class="comment">/**********************************</span></span><br><span class="line"><span class="comment">         初始化链表</span></span><br><span class="line"><span class="comment">输入值：链表的指针</span></span><br><span class="line"><span class="comment">输出值：状态码</span></span><br><span class="line"><span class="comment">功能：  将所以节点的游标指向后一个节点</span></span><br><span class="line"><span class="comment"> ***********************************/</span></span><br><span class="line"><span class="function">Status <span class="title">initLink</span><span class="params">(staticlink space)</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">  <span class="keyword">int</span> i;</span><br><span class="line">  <span class="keyword">for</span>(i=<span class="number">0</span>;i&lt;(MAX<span class="number">-1</span>);i++)&#123;  <span class="comment">//遍历所有节点</span></span><br><span class="line">    space[i].cur = i+<span class="number">1</span>;　<span class="comment">//将节点的游标指向下个节点</span></span><br><span class="line">  &#125;</span><br><span class="line">  space[MAX<span class="number">-1</span>].cur = <span class="number">0</span>; <span class="comment">//最后一个节点的游标指向第一个节点</span></span><br><span class="line">  <span class="keyword">return</span> OK;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="comment">/*********************************</span></span><br><span class="line"><span class="comment">         分配备用空间</span></span><br><span class="line"><span class="comment">输入值：链表的指针</span></span><br><span class="line"><span class="comment">输出值：备用节点的下标</span></span><br><span class="line"><span class="comment">功能：  将备用节点的分配出来使用</span></span><br><span class="line"><span class="comment"> *********************************/</span></span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">mallocSpace</span><span class="params">(staticlink space)</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">  <span class="keyword">int</span> i;</span><br><span class="line">  i = space[<span class="number">0</span>].cur;　<span class="comment">//取出第一个备用节点</span></span><br><span class="line">  <span class="keyword">if</span>(space[<span class="number">0</span>].cur)　　　　 <span class="comment">//如果取出成功</span></span><br><span class="line">    space[<span class="number">0</span>].cur = space[i].cur; <span class="comment">//第一个节点的指针往后移动</span></span><br><span class="line">  <span class="keyword">return</span> i;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="comment">/********************************</span></span><br><span class="line"><span class="comment">         获取长度</span></span><br><span class="line"><span class="comment">输入值：链表的指针</span></span><br><span class="line"><span class="comment">输出值：长度值</span></span><br><span class="line"><span class="comment">功能：  将链表中已用的节点个数返回</span></span><br><span class="line"><span class="comment"> ********************************/</span></span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">getLength</span><span class="params">(staticlink space)</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">  <span class="keyword">int</span> mov = MAX<span class="number">-1</span>;</span><br><span class="line">  <span class="keyword">int</span> j=<span class="number">0</span>;</span><br><span class="line">  <span class="keyword">while</span>(space[mov].cur)</span><br><span class="line">  &#123;　<span class="comment">//遍历所有已用节点</span></span><br><span class="line">    mov = space[mov].cur;</span><br><span class="line">    j++;</span><br><span class="line">  &#125;</span><br><span class="line">  <span class="keyword">return</span> j;</span><br><span class="line">&#125;</span><br><span class="line"><span class="comment">/*********************************</span></span><br><span class="line"><span class="comment">          创建值</span></span><br><span class="line"><span class="comment">输入值：链表的指针，初始值个数</span></span><br><span class="line"><span class="comment">输出值：状态码</span></span><br><span class="line"><span class="comment">功能：  为链表初始指定个数的随机值</span></span><br><span class="line"><span class="comment"> *********************************/</span></span><br><span class="line"><span class="function">Status <span class="title">createValue</span><span class="params">(staticlink space,<span class="keyword">int</span> num)</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">  srand(time(<span class="number">0</span>));</span><br><span class="line">  <span class="keyword">int</span> i,mov = MAX<span class="number">-1</span>;</span><br><span class="line">  space[mov].cur = <span class="number">1</span>;</span><br><span class="line">  <span class="keyword">for</span>(i=<span class="number">0</span>;i&lt;num;i++)</span><br><span class="line">  &#123;</span><br><span class="line">    mov = space[mov].cur;　　　　<span class="comment">//移动游标</span></span><br><span class="line">    space[mov].data = rand()%<span class="number">100</span>+<span class="number">1</span>;　　<span class="comment">//初始化随机值</span></span><br><span class="line">  &#125;</span><br><span class="line">  space[<span class="number">0</span>].cur = space[mov].cur;<span class="comment">//第一节点游标指向备用节点</span></span><br><span class="line">  space[mov].cur = <span class="number">0</span>;　 <span class="comment">//最后一个已用节点指向第一个节点</span></span><br><span class="line">  <span class="keyword">return</span> OK;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="comment">/*********************************</span></span><br><span class="line"><span class="comment">          插入节点</span></span><br><span class="line"><span class="comment">输入值：链表的指针，插入位置(从1开始)，插入位置</span></span><br><span class="line"><span class="comment">输出值：状态码</span></span><br><span class="line"><span class="comment">功能：  在指定的位置插入指定的值</span></span><br><span class="line"><span class="comment"> *********************************/</span></span><br><span class="line"><span class="function">Status <span class="title">insertNode</span><span class="params">(staticlink space,<span class="keyword">int</span> index,ElemType e)</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">  <span class="keyword">int</span> <span class="keyword">new</span>,mov,i;</span><br><span class="line">  <span class="keyword">if</span>(index&lt;<span class="number">1</span> || index&gt;getLength(space))<span class="keyword">return</span> ERROR;  <span class="comment">//不可以超过已用节点个数</span></span><br><span class="line"></span><br><span class="line">  mov = MAX<span class="number">-1</span>;</span><br><span class="line">  <span class="keyword">new</span> = mallocSpace(space);</span><br><span class="line"></span><br><span class="line">  <span class="keyword">if</span>(<span class="keyword">new</span>)&#123;</span><br><span class="line">    space[<span class="keyword">new</span>].data=e;　<span class="comment">//创建新节点</span></span><br><span class="line">    <span class="keyword">for</span>(i=<span class="number">1</span>;i&lt;index;i++)<span class="comment">//定位插入节点的前一节点</span></span><br><span class="line">      mov = space[mov].cur;</span><br><span class="line"></span><br><span class="line">    space[<span class="keyword">new</span>].cur = space[mov].cur;　<span class="comment">//连后</span></span><br><span class="line">    space[mov].cur = <span class="keyword">new</span>;　　<span class="comment">//接前</span></span><br><span class="line">    <span class="keyword">return</span> OK;</span><br><span class="line">  &#125;</span><br><span class="line">  <span class="keyword">return</span> ERROR;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="comment">/************************************</span></span><br><span class="line"><span class="comment">          删除节点</span></span><br><span class="line"><span class="comment">输入值：链表的指针，删除位置(从1开始)</span></span><br><span class="line"><span class="comment">输出值：状态码</span></span><br><span class="line"><span class="comment">功能：  删除指定的节点</span></span><br><span class="line"><span class="comment"> ************************************/</span></span><br><span class="line"><span class="function">Status <span class="title">deleteNode</span><span class="params">(staticlink space,<span class="keyword">int</span> index)</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">  <span class="keyword">if</span>(index&lt;<span class="number">1</span> || index&gt;getLength(space))<span class="keyword">return</span> ERROR;</span><br><span class="line">  <span class="keyword">int</span> mov,next,i;</span><br><span class="line"></span><br><span class="line">  mov = MAX<span class="number">-1</span>;</span><br><span class="line">  <span class="keyword">for</span>(i=<span class="number">1</span>;i&lt;index;i++)　<span class="comment">//定位删除节点的前一节点</span></span><br><span class="line">    mov = space[mov].cur;</span><br><span class="line"></span><br><span class="line">  next = space[mov].cur;<span class="comment">//获取被删节点</span></span><br><span class="line">  space[mov].cur = space[next].cur; <span class="comment">//前一节点连接被删节点的游标</span></span><br><span class="line">  freeNode(space,next);<span class="comment">//释放被删节点</span></span><br><span class="line">  <span class="keyword">return</span> OK;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="comment">/***********************************</span></span><br><span class="line"><span class="comment">          释放节点</span></span><br><span class="line"><span class="comment">输入值：链表的指针，释放节点的位置</span></span><br><span class="line"><span class="comment">输出值：状态码</span></span><br><span class="line"><span class="comment">功能:   将已用节点释放成备用节点</span></span><br><span class="line"><span class="comment"> ***********************************/</span></span><br><span class="line"><span class="function">Status <span class="title">freeNode</span><span class="params">(staticlink space,<span class="keyword">int</span> target)</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">  space[target].cur = space[<span class="number">0</span>].cur;<span class="comment">//释放节点连接第一备用节点</span></span><br><span class="line">  space[<span class="number">0</span>].cur = target;<span class="comment">//第一节点连接释放节点</span></span><br><span class="line">  <span class="keyword">return</span> OK;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="comment">/**********************************</span></span><br><span class="line"><span class="comment">          输出链表</span></span><br><span class="line"><span class="comment">输入值：链表的指针</span></span><br><span class="line"><span class="comment">输出值：状态码</span></span><br><span class="line"><span class="comment">功能：  将链表的值一一输出</span></span><br><span class="line"><span class="comment"> **********************************/</span></span><br><span class="line"><span class="function">Status <span class="title">printLink</span><span class="params">(staticlink space)</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">  <span class="keyword">int</span> mov = MAX<span class="number">-1</span>;</span><br><span class="line">  <span class="keyword">while</span>(space[mov].cur)</span><br><span class="line">  &#123;</span><br><span class="line">    mov = space[mov].cur;</span><br><span class="line">    <span class="built_in">printf</span>(<span class="string">"[%d] "</span>,space[mov].data);</span><br><span class="line">  &#125;</span><br><span class="line">  <span class="built_in">printf</span>(<span class="string">"\n"</span>);</span><br><span class="line">  <span class="keyword">return</span> OK;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">main</span><span class="params">()</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">  <span class="keyword">int</span> num,value,index;</span><br><span class="line">  staticlink L;</span><br><span class="line">  initLink(L);</span><br><span class="line"></span><br><span class="line">  <span class="built_in">printf</span>(<span class="string">"[create]enter num:"</span>);</span><br><span class="line">  <span class="built_in">scanf</span>(<span class="string">"%d"</span>,&amp;num);</span><br><span class="line">  createValue(L,num);</span><br><span class="line">  printLink(L);</span><br><span class="line"></span><br><span class="line">  <span class="built_in">printf</span>(<span class="string">"[insert]enter index:"</span>);</span><br><span class="line">  <span class="built_in">scanf</span>(<span class="string">"%d"</span>,&amp;index);</span><br><span class="line">  <span class="built_in">printf</span>(<span class="string">"[insert]enter value:"</span>);</span><br><span class="line">  <span class="built_in">scanf</span>(<span class="string">"%d"</span>,&amp;value);</span><br><span class="line">  insertNode(L,index,value);</span><br><span class="line">  printLink(L);</span><br><span class="line"></span><br><span class="line">  <span class="built_in">printf</span>(<span class="string">"[delete]enter index:"</span>);</span><br><span class="line">  <span class="built_in">scanf</span>(<span class="string">"%d"</span>,&amp;index);</span><br><span class="line">  deleteNode(L,index);</span><br><span class="line">  printLink(L);</span><br><span class="line">  <span class="keyword">return</span> <span class="number">0</span>;</span><br></pre></td></tr></table></figure>
<p>这次就先到这里吧。更多精彩内容，请期待下回分解。</p>
<p>另外：部分资料参考自网络，来源和作者实在无法考证，如果有侵犯到您的劳动成果，请速与我联系。</p>
<p>========================END=======================</p>

    </div>

    <div class="post-footer">   
        <div>
            
                转载声明：商业转载请联系作者获得授权,非商业转载请注明出处 © <a href="" target="_blank">infinitor</a>
            
        </div>
        <div>
            
        </div>  
    </div>
</article>

<div class="article-nav prev-next-wrap clearfix">
    
        <a href="/2018/02/18/数据结构-静态链表代码-C-类模板封装/" class="pre-post btn btn-default"><i class="fa fa-angle-left fa-fw"></i>上一篇</a>
    
    
        <a href="/2018/02/18/数据结构-线性表-顺序表-链表-上/" class="next-post btn btn-default">下一篇<i class="fa fa-angle-right fa-fw"></i></a>
    
</div>


    <div id="comments">
        
	
  <script id="dsq-count-scr" src="https://snippet.disqus.com/count.js" async></script>


<script type="text/javascript">
  var disqus_config = function () {
    this.page.url = 'http://yoursite.com/2018/02/18/数据结构-线性表-顺序表-链表-中/';
    this.page.identifier = '2018/02/18/数据结构-线性表-顺序表-链表-中/';
    this.page.title = '数据结构-线性表|顺序表|链表(中)';
  };
  var d = document, s = d.createElement('script');
  s.src = 'https://snippet.disqus.com/embed.js';
  s.setAttribute('data-timestamp', '' + +new Date());
  (d.head || d.body).appendChild(s);
</script>


	

    </div>





                </main>
                
    <aside class="col-md-4 sidebar">
        
        
    <div class="widget">    
        <h3 class="title">搜索</h3>
        <div id="search-form">
            <div id="result-mask" class="hide"></div>
            <div class="search-area">
                
                    <input id="search-key" type="search" autocomplete="off" placeholder="搜点什么呢?">
                    <button type="button" class="search-form-submit" id="search-local">站内搜索</button>
                
                
                    <form action="//google.com/search" method="get" accept-charset="UTF-8" class="search-form"><input type="search" name="q" class="search-form-input" placeholder="Google Search"><button type="submit" class="search-form-submit">谷歌搜索</button><input type="hidden" name="sitesearch" value="http://yoursite.com"></form>
                
            </div>
            <div id="result-wrap" class="hide">
                <div id="search-result"></div>
            </div>
            <div class="hide">
                <template id="search-tpl">
                    <div class="item">
                        <a href="/{path}" title="{title}">
                            <div class="title">{title}</div>
                            <div class="content">{content}</div>
                        </a>
                    </div>
                </template>
            </div>
        </div>
    </div>

        
        
    <div class="widget notification">
        <h3 class="title">网站公告</h3>
        <div>
            <p>大家好，欢迎来到我的个人博客。这里记录了我的成长过程，如果能帮到你一点点，我很开心。 <br/>
</p>
        </div>
    </div>

        
        
    <div class="widget">
      <h3 class="title">社交</h3> 
        <div class="content social">
            
	            <a href="//github.com/xiaoshiyisss" rel="external nofollow" title="Github" target="_blank">
			    	<i class="git fa fa-git"></i>
			    </a>
            
	            <a href="mailto:2638512393@qq.com" rel="external nofollow" title="邮箱" target="_blank">
			    	<i class="envelope-o fa fa-envelope-o"></i>
			    </a>
            
	            <a href="/" rel="external nofollow" title="联系QQ" target="_blank">
			    	<i class="qq fa fa-qq"></i>
			    </a>
            
	            <a href="/" rel="external nofollow" title="微博" target="_blank">
			    	<i class="weibo fa fa-weibo"></i>
			    </a>
            
	            <a href="/" rel="external nofollow" title="QQ群" target="_blank">
			    	<i class="users fa fa-users"></i>
			    </a>
            
	            <a href="/atom.xml" rel="external nofollow" title="RSS" target="_blank">
			    	<i class="feed fa fa-feed"></i>
			    </a>
            
        </div>
    </div>


        
        
    <div class="widget">
        <h3 class="title">分类</h3>
        <ul class="category-list"><li class="category-list-item"><a class="category-list-link" href="/categories/全栈/"><i class="fa" aria-hidden="true">全栈</i></a><span class="category-list-count">1</span></li><li class="category-list-item"><a class="category-list-link" href="/categories/数据结构/"><i class="fa" aria-hidden="true">数据结构</i></a><span class="category-list-count">4</span></li><li class="category-list-item"><a class="category-list-link current" href="/categories/算法/"><i class="fa" aria-hidden="true">算法</i></a><span class="category-list-count">6</span></li><li class="category-list-item"><a class="category-list-link" href="/categories/随想/"><i class="fa" aria-hidden="true">随想</i></a><span class="category-list-count">1</span></li></ul>
    </div>


        
        
    <div class="widget">
      <h3 class="title">归档</h3>
        <ul class="archive-list"><li class="archive-list-item"><a class="archive-list-link" href="/archives/2018/05/"><i class="fa" aria-hidden="true">May 2018</i></a><span class="archive-list-count">3</span></li><li class="archive-list-item"><a class="archive-list-link" href="/archives/2018/02/"><i class="fa" aria-hidden="true">February 2018</i></a><span class="archive-list-count">9</span></li></ul>
    </div>


        
        
  <div class="widget">
    <h3 class="title">标签云</h3>
    <div class="content tag-cloud">
        <a href="/tags/Python-游戏/" style="font-size: 10px;">Python, 游戏</a> <a href="/tags/数据结构/" style="font-size: 15px;">数据结构</a> <a href="/tags/算法/" style="font-size: 20px;">算法</a> <a href="/tags/随想/" style="font-size: 10px;">随想</a>
    </div>
  </div>


        
        
    <div class="widget">
        <h3 class="title">友链</h3>
        <div class="content friends-link">
        
            <a href="https://www.csdn.net/" class="fa" target="_blank">CSDN</a>
        
            <a href="https://www.cnblogs.com/" class="fa" target="_blank">博客园</a>
        
        </div>
    </div>


        
    </aside>

            </div>
        </div>
    </section>
    <footer class="main-footer">
    <div class="container">
        <div class="row">
        </div>
    </div>
</footer>

<a id="back-to-top" class="hide">
	<i class="fa fa-chevron-up"></i>
</a>




    <div class="copyright">
    <div class="container">
        <div class="row">
            <div class="col-sm-12"> 
                <span>Copyright &copy; 2017
                </span> | 
                <span>
                    Powered by <a href="//hexo.io" class="copyright-links" target="_blank" rel="nofollow">Hexo</a>
                </span> | 
                <span>
                    Theme by <a href="//github.com/shenliyang/hexo-theme-snippet.git" class="copyright-links" target="_blank" rel="nofollow">Snippet</a>
                </span>
            </div>
        </div>
    </div>
</div>



	<script src="/js/search.js?rev=@@hash"></script>


<script src="/js/app.js?rev=@@hash"></script>


</body>
</html>